Zkouška Holan - Pergel 2. 6. 2025

Úloha Poštmistra Antonína

Poštmistr Antonín půjde do důchodu a chce se pomstít svému zaměstnavateli. Tento týden jde naposled do práce, rozpis práce má v souborech po.txt, ut.txt, st.txt, ct.txt, pa.txt, v každém je na prvním řádku číslo n (~1000) jako počet balíků, které mu přijedou po páse, a následně na n řádcích čísla x y z p jako tři rozměry (10–130 cm) přijíždějící krabice a případně příznak "neklopit".

Jeho cílem je postavit co nejvyšší věž z balíků a na konci dne ji zapálit. Krabici může buď vypravit / spálit / shodit do jámy / zlikvidovat / prostě nepoužít, nebo ji postavit na vrchol dosavadní věže. Smí pokládat pouze krabice s menší podstavou na krabice s větší podstavou (v obou směrech, tj. horní krabice nikde nesmí přečnívat). Krabice bez příznaku "neklopit" smí otáčet po všech třech osách (vždy o 90°, ne našikmo), krabice s příznakem "neklopit" smí otáčet pouze v jedné ose (vyberte si, která z os x/y/z je výška, to zapište do upřesnění zadání).

Výstupem vašeho programu je: 1) den, kdy má pomstu provést (pomsta proběhne v jeden den, ve zbylých bude pracovat normálně), 2) celková výška postavené věže, 3) popis postupu, které krabice postavit do věže a jak je natočit (přesný formát popisu není určen).

Program by neměl zabírat víc než 1 GB RAM, disku je asi neomezeně.

Výstupem psané části je papír se všemi vašimi myšlenkami a shrnutí obsahující

  1. upřesnění zadání

  2. postřehy

  3. zdůvodněnou volnu algoritmu

  4. reprezentaci dat

  5. dekompozici programu

  6. diskuzi

Časový limit na psanou část jsou 2 hodiny samostatné práce (tomu ještě předchází instrukce, zadání zadání a otázky).

Na ústní u Holana se mě ještě zeptal na dynamické programování (nevím jestli kvůli tomu, že na to byla i psaná část) a vypočítával jsem mu na papír počty binárních stromů na n prvcích.

Přišel tam v jeho legendární zelený mikině, nemusíte si brát oblek nebo něco.